package com.niuke;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

/**
 * 25. 组装最大可靠性设备
 * 可靠性越高的器件其价格price越贵
 * https://zhuanlan.zhihu.com/p/638852557
 */
public class NiukeMoni25 {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        /**
         * 500 3
         * 6
         * 0 80 100
         * 0 90 200
         * 1 50 50
         * 1 70 210
         * 2 50 100
         * 2 60 150
         */
        String[] line1 = scanner.nextLine().split(" ");
        int yuSuan = Integer.parseInt(line1[0]); // 预算
        int needType = Integer.parseInt(line1[1]); // 需要的元件数量，编号从0开始
        int allData = Integer.parseInt(scanner.nextLine()); // 提供的数据量

        int[] minPrice = new int[needType]; // 每个元件可靠性都选最低的价格，如果超出预算，可以返回 -1
        int[] minRel = new int[needType]; // 为了能更快得到一个特殊答案创建的一个临时数组

        int[] maxResult = new int[needType]; // 木桶原理，各个元件可靠性最高的数组，取最小值就是首先想到的答案

        Map<Integer, List<int[]>> data = new HashMap<>();

        for (int i = 0; i < allData; i++) {
            String[] item = scanner.nextLine().split(" ");
            Integer type = Integer.parseInt(item[0]);
            Integer rel = Integer.parseInt(item[1]);
            Integer pri = Integer.parseInt(item[2]);

            List<int[]> dataItem = data.getOrDefault(type, new ArrayList<>());
            if (dataItem.size() == 0) {
                maxResult[type] = rel;
                minPrice[type] = pri;
                minRel[type] = rel;
            } else {
                maxResult[type] = Math.max(maxResult[type], rel);
                minPrice[type] = Math.min(minPrice[type], pri);
                minRel[type] = Math.min(minRel[type], rel);
            }
            dataItem.add(new int[]{rel, pri});
            data.put(type, dataItem);
        }

        int result = -1;

        int minPriceSum = Arrays.stream(minPrice).sum();
        if (minPriceSum == yuSuan) {
            result = Arrays.stream(minRel).min().getAsInt();
        } else if (minPriceSum < yuSuan) {
            for (Integer type : data.keySet()) {
                List<int[]> item = data.get(type);
                item.sort(new Comparator<int[]>() {
                    @Override
                    public int compare(int[] ints, int[] t1) {
                        return ints[0] - t1[0];
                    }
                });
                data.put(type, item);
            }

            int maxRel = Integer.MAX_VALUE;
            int maxType = -1;

            for (int i = 0; i < maxResult.length; i++) {
                if (maxRel > maxResult[i]) {
                    maxRel = maxResult[i];
                    maxType = i;
                }
            }

            while (result == -1) { // 一定有解，所以得不到解不退出循环
                int allPrice = 0;
                int index = 0;
                for (Integer type : data.keySet()) {
                    List<int[]> item = data.get(type);
                    if (type == maxType) {
                        for (int i = 0; i < item.size(); i++) {
                            int[] curr = item.get(i);
                            if (curr[0] == maxRel) {
                                allPrice += curr[1];
                                index = i;
                                break;
                            }
                        }
                    } else {
                        for (int i = 0; i < item.size(); i++) {
                            int[] curr = item.get(i);
                            if (curr[0] >= maxRel) {
                                allPrice += curr[1];
                                break;
                            }
                        }
                    }
                }

                if (allPrice <= yuSuan) {
                    result = maxRel;
                } else {
                    maxRel = data.get(maxType).get(index - 1)[0];
                }
            }
        }

        System.out.println(result);
    }

}
